Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > Consider the languages:L1 = {wwR |w ∈ {...
Start Learning for Free
Consider the languages:
L1 = {wwR |w ∈ {0, 1}*}
L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbol
L3 = {ww | w ∈ (0, 1}*)
L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbol
L3 = {ww | w ∈ (0, 1}*)
Q. Which one of the following is TRUE?
- a)L1 is a deterministic CFL
- b)L2 is a deterministic CFL
- c)L3 is a CFL, but not a deterministic CFL
- d)L3 is a deterministic CFL
Correct answer is option 'B'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ...
L1: {ww^R | w belongs {0,1}*} This is a CFL but not a DCFL. It can be derived from the following grammar S -> aSa | bSb | epsilon But it can't be derived from any deterministic pushdown automaton, because there is no way to figure out where a word w ends and its reverse starts. L2: {w#w^R | w belongs {0,1}*} This is a CFL, due to the same reason as described above. This is a deterministic CFL because we have a marker to help us find out the end of the word w and start of its reverse. Thus a PDA where all the alphabets are pushed until we get # and afterwards pop only if the top of the stack matches the current alphabet and reject otherwise - will derive L2. L3: {ww | w belongs {0,1}*} This is not even a CFL. Above claim could be proved using pumping lemma - Consider a string z of the form (0^n 1^n 0^n 1^n). Assuming L3 is a CFL, and z obviously satisfies L3 - thus z should also satisfy pumping lemma. We will take n such that n = p, where p is the pumping length of L3, hence forcing our string to be of length greater than pumping length. Now, according to pumping lemma, there must exist u,v,w,x,y such that z = uvwxy, |vwx| <= p, |vx| > 0 and u{v^i}x{y^i}z belongs L3 for all i>=0. There doesn't exist any such configuration of u,v,w,x,y such that u{v^0}x{y^0}z belongs L3. Hence z doesn't satisfy pumping lemma. Hence L3 is not a CFL. Considering all the above conclusions, only correct option comes out to be (B) L2 is a deterministic CFL.
Most Upvoted Answer
Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ...
Explanation:
L1 = {wwR | w {0, 1}*}
- L1 is the language of all strings of the form wwR, where w is any string of 0s and 1s, and wR is the reverse of w.
- This language can be recognized by a non-deterministic pushdown automaton (NPDA) but not by a deterministic pushdown automaton (DPDA).
- Therefore, L1 is not a deterministic context-free language (CFL).
L2 = {w#wR | w {0, 1}*}
- L2 is the language of all strings of the form w#wR, where w is any string of 0s and 1s, and # is a special symbol.
- This language can be recognized by a deterministic pushdown automaton (DPDA) by pushing all symbols until the # is encountered, then popping symbols while matching them against the remaining input.
- Therefore, L2 is a deterministic context-free language (CFL).
L3 = {ww | w (0, 1}*)
- L3 is the language of all strings of the form ww, where w is any non-empty string of 0s and 1s.
- This language can be recognized by a non-deterministic pushdown automaton (NPDA) but not by a deterministic pushdown automaton (DPDA).
- Therefore, L3 is a context-free language (CFL) but not a deterministic CFL.
Therefore, the correct answer is: L2 is a deterministic CFL.
L1 = {wwR | w {0, 1}*}
- L1 is the language of all strings of the form wwR, where w is any string of 0s and 1s, and wR is the reverse of w.
- This language can be recognized by a non-deterministic pushdown automaton (NPDA) but not by a deterministic pushdown automaton (DPDA).
- Therefore, L1 is not a deterministic context-free language (CFL).
L2 = {w#wR | w {0, 1}*}
- L2 is the language of all strings of the form w#wR, where w is any string of 0s and 1s, and # is a special symbol.
- This language can be recognized by a deterministic pushdown automaton (DPDA) by pushing all symbols until the # is encountered, then popping symbols while matching them against the remaining input.
- Therefore, L2 is a deterministic context-free language (CFL).
L3 = {ww | w (0, 1}*)
- L3 is the language of all strings of the form ww, where w is any non-empty string of 0s and 1s.
- This language can be recognized by a non-deterministic pushdown automaton (NPDA) but not by a deterministic pushdown automaton (DPDA).
- Therefore, L3 is a context-free language (CFL) but not a deterministic CFL.
Therefore, the correct answer is: L2 is a deterministic CFL.
Attention Computer Science Engineering (CSE) Students!
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Similar Computer Science Engineering (CSE) Doubts
Top Courses for Computer Science Engineering (CSE)View all
Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbolL3 = {ww | w ∈ (0, 1}*)Q. Which one of the following is TRUE?a)L1 is a deterministic CFLb)L2 is a deterministic CFLc)L3 is a CFL, but not a deterministic CFLd)L3 is a deterministic CFLCorrect answer is option 'B'. Can you explain this answer?
Question Description
Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbolL3 = {ww | w ∈ (0, 1}*)Q. Which one of the following is TRUE?a)L1 is a deterministic CFLb)L2 is a deterministic CFLc)L3 is a CFL, but not a deterministic CFLd)L3 is a deterministic CFLCorrect answer is option 'B'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbolL3 = {ww | w ∈ (0, 1}*)Q. Which one of the following is TRUE?a)L1 is a deterministic CFLb)L2 is a deterministic CFLc)L3 is a CFL, but not a deterministic CFLd)L3 is a deterministic CFLCorrect answer is option 'B'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbolL3 = {ww | w ∈ (0, 1}*)Q. Which one of the following is TRUE?a)L1 is a deterministic CFLb)L2 is a deterministic CFLc)L3 is a CFL, but not a deterministic CFLd)L3 is a deterministic CFLCorrect answer is option 'B'. Can you explain this answer?.
Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbolL3 = {ww | w ∈ (0, 1}*)Q. Which one of the following is TRUE?a)L1 is a deterministic CFLb)L2 is a deterministic CFLc)L3 is a CFL, but not a deterministic CFLd)L3 is a deterministic CFLCorrect answer is option 'B'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbolL3 = {ww | w ∈ (0, 1}*)Q. Which one of the following is TRUE?a)L1 is a deterministic CFLb)L2 is a deterministic CFLc)L3 is a CFL, but not a deterministic CFLd)L3 is a deterministic CFLCorrect answer is option 'B'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbolL3 = {ww | w ∈ (0, 1}*)Q. Which one of the following is TRUE?a)L1 is a deterministic CFLb)L2 is a deterministic CFLc)L3 is a CFL, but not a deterministic CFLd)L3 is a deterministic CFLCorrect answer is option 'B'. Can you explain this answer?.
Solutions for Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbolL3 = {ww | w ∈ (0, 1}*)Q. Which one of the following is TRUE?a)L1 is a deterministic CFLb)L2 is a deterministic CFLc)L3 is a CFL, but not a deterministic CFLd)L3 is a deterministic CFLCorrect answer is option 'B'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE).
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbolL3 = {ww | w ∈ (0, 1}*)Q. Which one of the following is TRUE?a)L1 is a deterministic CFLb)L2 is a deterministic CFLc)L3 is a CFL, but not a deterministic CFLd)L3 is a deterministic CFLCorrect answer is option 'B'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbolL3 = {ww | w ∈ (0, 1}*)Q. Which one of the following is TRUE?a)L1 is a deterministic CFLb)L2 is a deterministic CFLc)L3 is a CFL, but not a deterministic CFLd)L3 is a deterministic CFLCorrect answer is option 'B'. Can you explain this answer?, a detailed solution for Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbolL3 = {ww | w ∈ (0, 1}*)Q. Which one of the following is TRUE?a)L1 is a deterministic CFLb)L2 is a deterministic CFLc)L3 is a CFL, but not a deterministic CFLd)L3 is a deterministic CFLCorrect answer is option 'B'. Can you explain this answer? has been provided alongside types of Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbolL3 = {ww | w ∈ (0, 1}*)Q. Which one of the following is TRUE?a)L1 is a deterministic CFLb)L2 is a deterministic CFLc)L3 is a CFL, but not a deterministic CFLd)L3 is a deterministic CFLCorrect answer is option 'B'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice Consider the languages:L1 = {wwR |w ∈ {0, 1}*}L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbolL3 = {ww | w ∈ (0, 1}*)Q. Which one of the following is TRUE?a)L1 is a deterministic CFLb)L2 is a deterministic CFLc)L3 is a CFL, but not a deterministic CFLd)L3 is a deterministic CFLCorrect answer is option 'B'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Suggested Free Tests
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup